package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Stack;

/**
 * 描述：
 * 给定一个整数数组 asteroids，表示在同一行的小行星。
 * <p>
 * 对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
 * <p>
 * 找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/XagZNi
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * <p>
 * 解题思路：
 * 1.使用栈记录往右方向的数据 顺序入栈 碰到往左的数据 则出栈进行判断 如果栈空 则入栈并继续往下遍历 直到数组遍历完
 * 2.如果栈为空 则碰到往左的直接入栈
 *
 * @author 🧑 ‍wanwei
 * @since 2022-10-21 10:12
 */
public class CK小行星碰撞 {

    public static void main(String[] args) {
        int[] asteroids = {8,-8};

        int[] ints = asteroidCollision(asteroids);

        PrintUtil.print(ints);
    }

    public static int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack();

        for (int i = 0; i < asteroids.length; i++) {
            if (asteroids[i] < 0) {
                if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(asteroids[i]);
                } else {
                    while (!stack.isEmpty() && stack.peek() > 0 && (stack.peek() + asteroids[i] < 0)) {
                        stack.pop();
                    }
                    if (stack.isEmpty() || stack.peek() < 0) {
                        stack.push(asteroids[i]);
                    }else if(!stack.isEmpty() && stack.peek() + asteroids[i] == 0){
                        stack.pop();
                    }
                }
            } else {
                stack.push(asteroids[i]);
            }
        }
        int[] array = new int[stack.size()];
        int i = 1;
        while (!stack.isEmpty()) {
            array[array.length - i] = stack.pop();
            i++;
        }
        return array;
    }
}
